#include <iostream>

#include <omp.h>

#include "ogsolverBBPv4openMP.h"

/**
 * A BBP solver : starts with jobs with last due dates
 *
 * Dans cette version 3 de la BBP, on demarre avec les jobs reordonnes dans le sens des dates dues croissantes. Mais
 * contrairement a l'exploration brutale de la version 2, cette fois on ne considere pas n'importe quel numero de batch.
 * Pour chaque job, on choisit de le rajouter soit dans un batch deja existant dont la capacite residuel est suffisante
 * pour stocker le nouveau job, soit dans un nouveau batch.
 *
 * Le nouveau batch est ordonnance avant les autres batchs deja crees.
 *
 * ATTENTION : Pour que cette solution soit optimale, sachant que l'on
 * part d'un probleme pour lequel les jobs sont classes par date due croissante, il est egalement necessaire que le cout de stockage
 * de tous les jobs soient identiques. Dans le cas contraire, la solution ainsi construite n'est plus certaine d'etre optimale.
 */
OGSolverBBPv4openMPrecursive::OGSolverBBPv4openMPrecursive(GSupplyLinkProblem& pb):OGSolverBBPv3(pb) {
}

OGSolverBBPv4openMPrecursive::~OGSolverBBPv4openMPrecursive() {
//    if (this->bestSolution != NULL ) delete this->bestSolution ;
//    if (this->bestSolutionDueDateOrdered != NULL ) delete this->bestSolutionDueDateOrdered ;
//    if (this->currentSolutionDueDateOrdered != NULL ) delete this->currentSolutionDueDateOrdered ;
}

/**
 *
 */
void OGSolverBBPv4openMPrecursive::solveMain() {
    cout << "BBPv4 OpenMP recursive" << endl ;

//    vector<double> tabBatchRemainingCapacity(maxBatch) ;
//    for (int b=0;b<maxBatch;b++)
//        tabBatchRemainingCapacity[b] = this->problem.getTransporter(0).getCapacity() ;
    vector<double> tabBatchRemainingCapacity ;

    // Multi processes
    cout << "depthFirstSearchMulti() started" << endl ;
    depthFirstSearchMultiRecursive(0, this->problem.getNP()-1, this->currentSolutionDueDateOrdered, tabBatchRemainingCapacity) ;

}

/**
 *
 */
void OGSolverBBPv4openMPrecursive::informationOpenMP() {
    int nthreads=0;             // number of thread available
    int threadid=0;             // id of thread
    // Information about parallelization
    #pragma omp parallel private(threadid)              // parallel region
    {
        #pragma omp master                              // only the master thread will execute this code
        {
            nthreads=omp_get_num_threads();             // computation of the total number of threads
            cout<<endl<<nthreads<<" thread(s) available for computation"<<endl;
        }

        #pragma omp barrier                             // barrier to display nthreads before threadid

        threadid=omp_get_thread_num();
        #pragma omp critical                            // in order to "protect" the common output
        {
            cout<<"Thread "<<threadid<<" is ready for computation"<<endl;
        }
    }
}

/**
 * DepthFirstSearch (BBP) with multi processes (Parallel with openMP)
 */
void OGSolverBBPv4openMPrecursive::depthFirstSearchMultiRecursive(int nbrbatch, int job, OGSupplyLinkSolutionPartial& sol, vector<double>& tabBatchRemainingCapacity) {

    int batchPotentialIndice = 0 ;
    int batchRealIndice=-1 ;
    int incnbrbatch = -1 ;
    vector<double> tabBatchRemainingCapacity2 ;
    OGSupplyLinkSolutionPartial sol2 ;
    int job2 ;
    double lowerBound ;
    int stoprecurs ;
    bool cut ;

    int threadid=0 ;


/* OpenMP example
    int N=0;                    // current tested number
    int n=0;                    // to check divisibility
    bool isprime=true;          // is N a prime ?

    #pragma omp parallel for private(n,isprime) schedule(dynamic)
    for(N=2;N<=500000;N++)
    {
        // Search for a divisor
        isprime=true;
        n=2;
        while(n<N&&isprime)
        {
            if(N%n==0)
                isprime=false;
            n++;
        }
    }
*/


   /* Compilation avec openMP :
       -fopenmp -L /usr/lib/gcc/i486-linux-gnu/4.4 -lgomp
    */

    #pragma omp parallel for private(batchRealIndice,incnbrbatch,tabBatchRemainingCapacity2,sol2,job2,lowerBound,stoprecurs,cut,threadid) schedule(dynamic)           // parallel region
    for (batchPotentialIndice=nbrbatch-1;batchPotentialIndice>=-1;batchPotentialIndice--) {
        // Add job in a batch, if batchjob==-1 => create a new batch before

        batchRealIndice=-1 ;
        incnbrbatch = -1 ;

        // Job is added to an existing batch
        if (batchPotentialIndice>=0 && tabBatchRemainingCapacity[batchPotentialIndice]>=this->problem.getJobSize(job)) {
            batchRealIndice= batchPotentialIndice ;
            incnbrbatch = 0 ;
        }

        // Creation of a new batch
        if (batchPotentialIndice<0) {
            batchRealIndice=0 ;
            incnbrbatch = 1 ;
        }

        // Transformation of the solution
        if (incnbrbatch>=0) {
            tabBatchRemainingCapacity2 = tabBatchRemainingCapacity ;
            sol2 = sol ;

            if (incnbrbatch>0) {
                tabBatchRemainingCapacity2.insert(tabBatchRemainingCapacity2.begin(),this->problem.getTransporter(0).getCapacity()) ;
                // The batch indices of previously placed jobs should be increased
                for (job2=job+1;job2<problem.getNP();job2++) {
                    sol2.setBatchIndice(job2,1+sol2.getBatchIndice(job2)) ;
                }
            }
            tabBatchRemainingCapacity2[batchRealIndice] -= this->problem.getJobSize(job) ;
            sol2.setBatchIndice(job, batchRealIndice+1) ;
            sol2.setDeliveryCompletionTime(job, (double)batchRealIndice+1) ;
            sol2.setNbrBatch(nbrbatch+incnbrbatch) ;

            lowerBound = sol2.evaluatePartial(job, this->problem.getNP()-1);
            assert (lowerBound>=0) ;

            stoprecurs=0 ;
            // Evaluation of the newly built solution
            if (job<=0) {
                sol2.evaluate() ;
                if (bestSolutionDueDateOrdered.getEvaluation()<0 || sol2.getEvaluation()<bestSolutionDueDateOrdered.getEvaluation()) {
                    #pragma omp critical
                    {
                        bestSolutionDueDateOrdered = sol2 ;
cout << "besteval=" << bestSolutionDueDateOrdered.getEvaluation() << endl ;
                    }
                }
                stoprecurs=1 ;
            }

            // Cut
            if (!stoprecurs) {
                cut = false ;
                if (bestSolutionDueDateOrdered.getEvaluation()>=0 && lowerBound>=bestSolutionDueDateOrdered.getEvaluation()) {
                    cut = true ;
                }
                if (!cut) {
                    depthFirstSearchMultiRecursive(nbrbatch+incnbrbatch, job-1, sol2, tabBatchRemainingCapacity2) ;
                }
            }
        }
    }
    #pragma omp nowait

}


